use rand::Rng;

const MILLER_TEST_COUNT : usize = 8;

fn exp_with_mod(mut base: u128, mut exp: u128, modulus: u128) -> u128 {
    let mut result = 1;
    base %= modulus;
    while exp > 0 {
        if exp % 2 == 1 {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exp >>= 1;
    }
    result
}

pub fn miller_rabin_test(x: u128) -> bool {
    // Miller-Rabin 素数测试，但只测试9以上的数
    if x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0 {
        return false;
    }
    let mut d = x - 1;
    let mut r: u32 = 0;
    while d % 2 == 0 {
        r += 1;
        d >>= 1;
    }
    let mut rng = rand::thread_rng();
    for _ in 0..MILLER_TEST_COUNT {
        let a = rng.gen_range(2..=x - 1);
        let mut t = exp_with_mod(a, d, x);
        if t == 1 || t == x - 1 {
            continue;
        }
        let mut composite = true;
        for _ in 0..(r - 1) {
            t = (t * t) % x;
            if t == x - 1 {
                composite = false;
                break;
            }
        }
        if composite {
            return false;
        }
    }
    true
}

pub fn min_edge_prime_num(number: u32) -> String {
    // 从边长为3的状态开始
    let mut num_count = 5;
    let mut prime_count = 3;
    let mut square_len = 3;
    let mut test_num = 9;
    while prime_count * 100 >= number * num_count {
        square_len += 2;
        for _ in 0..4 {
            // 检查四个顶点
            test_num += square_len - 1;
            prime_count += if miller_rabin_test(test_num) { 1 } else { 0 };
            num_count += 1;
        }
    }
    format!("{},{}", square_len, prime_count)
}
